﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Unit = System.UInt32;

namespace ArgusPCLib.Mathematics
{
	public class BigNumBase : ILinearScalar
	{
		#region Fields
		public const int UnitSize = 32;
		public const Unit UnitMaxValue = Unit.MaxValue;
		private const int MinUnits = 1;

		List<Unit> bits;
		#endregion

		#region Constructors
		protected BigNumBase(NumberProperties properties, List<Unit> bits)
		{
			this.Properties = Flags<NumberProperties>.FromEnum();
			if (bits != null)
				this.bits = bits;
			else
				this.bits = new List<Unit>();
			this.Properties.Value = properties;
			if (this.Properties.HasFlag(NumberProperties.IsInfinite))
				this.SetToInfinite();
			else if (this.Properties.HasFlag(NumberProperties.IsNaN))
				this.SetToNaN();
			else
				this.RemoveLeadingZeros();
		}

		protected BigNumBase(bool isNegative, bool fixedSize, List<Unit> bits)
			:this(NumberProperties.None, bits)
		{
			this._IsNegative = isNegative;
			this._FixedSize = fixedSize;
			this.RemoveLeadingZeros();
		}

		protected BigNumBase(BigNumBase integer)
			: this(integer.Properties.Value, new List<Unit>(integer.bits)) { }

		protected BigNumBase(BigNumBase integer, bool isNegative, bool fixedSize)
			: this(isNegative, fixedSize, new List<Unit>(integer.bits)) { }

		protected BigNumBase()
			: this(false, false, new List<Unit>()) { }

		protected BigNumBase(int size)
			: this(false, true, new List<Unit>(new Unit[size])) { }

		protected BigNumBase(int[] bits)
			: this((NumberProperties)bits.Last(), new List<Unit>(bits.Length - 1))
		{
			this.bits.Clear();
			for (int i = 0; i < bits.Length - 1; i++)
				this.bits.Add((Unit)bits[i]);
			this.RemoveLeadingZeros();
		}
		#endregion

		#region Properties
		protected static BigNumBase Zero { get { return new BigNumBase(); } }

		protected Flags<NumberProperties> Properties { get; private set; }
		protected bool _FixedSize
		{ 
			get { return this.Properties.HasFlag(NumberProperties.FixedSize); }
			private set { this.Properties.Value = this.Properties.SetFlag(NumberProperties.FixedSize, value); }
		}
		protected bool _IsNegative
		{
			get { return this.Properties.HasFlag(NumberProperties.IsNegative); }
			private set { this.Properties.Value = this.Properties.SetFlag(NumberProperties.IsNegative, value); }
		}
		protected bool _IsNaN
		{
			get { return this.Properties.HasFlag(NumberProperties.IsNaN); }
			private set { this.Properties.Value = this.Properties.SetFlag(NumberProperties.IsNaN, value); }
		}
		protected bool _IsInfinite
		{
			get { return this.Properties.HasFlag(NumberProperties.IsInfinite); }
			private set { this.Properties.Value = this.Properties.SetFlag(NumberProperties.IsInfinite, value); }
		}

		public int Units
		{
			get { return this.bits.Count; }
			set
			{
				if (this._FixedSize == false)
					throw new InvalidOperationException("FixedSize must be true to set the Unit count.");
				if (this.bits.Count > value)
					this.bits.RemoveRange(value, this.bits.Count - value);
				else if (this.bits.Count < value)
					this.bits.AddRange(new Unit[value - this.bits.Count]);
			}
		}

		public int this[int index] { get { return (int)this.bits[index]; } }
		#endregion

		#region Private Methods
		
		#endregion

		#region Protected Methods
		protected virtual void SetToZero()
		{
			this.Properties.Value = NumberProperties.None;
			int count;
			if (this._FixedSize == true)
			{
				count = this.Units;
				this.Properties.Value = this.Properties.SetFlag(NumberProperties.FixedSize, true);
			}
			else
			{
				count = BigNumBase.MinUnits;
			}

			this.bits.Clear();
			this.bits.AddRange(new Unit[count]);
		}

		protected virtual void SetToNaN()
		{
			this.SetToZero();
			this._IsNaN = true;
		}

		protected virtual void SetToInfinite()
		{
			bool isNegative = this._IsNegative;
			this.SetToZero();
			this._IsInfinite = true;
			this._IsNegative = isNegative;
		}

		protected void RemoveLeadingZeros()
		{
			if (this._FixedSize == false)
			{
				while (this.bits.Count > BigNumBase.MinUnits && this.bits.Last() == 0)
					this.bits.RemoveLast();
			}
			if (this.bits.Count < BigNumBase.MinUnits)
				this.bits.AddRange(new Unit[BigNumBase.MinUnits - this.bits.Count]);
		}

		protected void InsertLeft(bool bit)
		{
			this.ShiftLeft(1);
			if (bit == true)
			this.bits[0] |= 1;
		}

		protected void InsertLeft(int bits, int count)
		{
			this.ShiftLeft(count);
			this.bits[0] |= (uint)bits & (~0u >> (32 - count));
		}
		/// <summary>
		/// Performs a logical left shift.
		/// </summary>
		protected void ShiftLeft(int count)
		{
			int zeros = count / BigNumBase.UnitSize;
			int shift = count % BigNumBase.UnitSize;

			if (this._FixedSize == true && zeros > 0)
				this.bits.RemoveRange(this.bits.Count - zeros, zeros);

			if (shift > 0)
			{
				if (this._FixedSize == false && (this.bits[this.bits.Count - 1] >> (BigNumBase.UnitSize - shift)) != 0)
					this.bits.Add(0);
				else
					this.bits[this.bits.Count - 1] = this.bits[this.bits.Count - 1] << shift;

				for (int i = this.bits.Count - 2; i > -1; i--)
				{
					this.bits[i + 1] |= this.bits[i] >> (BigNumBase.UnitSize - shift);
					this.bits[i] = this.bits[i] << shift;
				}
			}

			this.bits.InsertRange(0, new Unit[zeros]);
		}

		/// <summary>
		/// Performs a logical right shift.
		/// </summary>
		protected void ShiftRight(int count)
		{
			int zeros = System.Math.Min(count / BigNumBase.UnitSize, this.Units);
			int shift = count % BigNumBase.UnitSize;

			if (zeros > 0)
				this.bits.RemoveRange(0, zeros);

			if (this.bits.Count > 0)
			{
				if (shift > 0)
				{
					this.bits[0] = this.bits[0] >> shift;

					for (int i = 1; i < this.bits.Count; i++)
					{
						this.bits[i - 1] |= this.bits[i] << (BigNumBase.UnitSize - shift);
						this.bits[i] = this.bits[i] >> shift;
					}
				}

				if (this._FixedSize == false)
				{
					while (this.bits.Count > 1 && this.bits[this.bits.Count - 1] == 0)
						this.bits.RemoveAt(this.bits.Count - 1);
				}
				else if (zeros > 0)
				{
					this.bits.AddRange(new Unit[zeros]);
				}
			}
			if (this.bits.Count < BigNumBase.MinUnits)
				this.bits.AddRange(new Unit[BigNumBase.MinUnits - this.bits.Count]);
		}

		protected void BitwiseAnd(BigNumBase integer)
		{
			int count = System.Math.Min(this.bits.Count, integer.bits.Count);
			if (this._FixedSize == false)
				this.Units = count;
			else
				count = System.Math.Min(this.Units, count);

			for (int i = 0; i < count; i++)
				this.bits[i] = this.bits[i] & integer.bits[i];

			if (this._FixedSize == true)
			{
				for (int i = count; i < this.Units; i++)
					this.bits[i] = 0;
			}
		}

		protected void BitwiseOr(BigNumBase integer)
		{
			List<Unit> min;
			List<Unit> max;
			if (this.bits.Count < integer.bits.Count)
			{
				min = this.bits;
				max = integer.bits;
			}
			else
			{
				min = integer.bits;
				max = this.bits;
			}

			int count1 = System.Math.Max(this.bits.Count, integer.bits.Count);
			if (this._FixedSize == false)
				this.Units = count1;
			else
				count1 = System.Math.Min(this.Units, count1);

			int count2 = System.Math.Min(count1, min.Count);

			for (int i = 0; i < count2; i++)
				this.bits[i] = min[i] | max[i];
			for (int i = count2; i < count1; i++)
				this.bits[i] = max[i];

			if (this._FixedSize == true)
			{
				for (int i = count1; i < this.Units; i++)
					this.bits[i] = 0;
			}
		}

		protected void BitwiseXor(BigNumBase integer)
		{
			List<Unit> min;
			List<Unit> max;
			if (this.bits.Count < integer.bits.Count)
			{
				min = this.bits;
				max = integer.bits;
			}
			else
			{
				min = integer.bits;
				max = this.bits;
			}

			int count1 = max.Count;
			if (this._FixedSize == false)
				this.Units = max.Count;
			else
				count1 = System.Math.Min(this.Units, count1);

			int count2 = System.Math.Min(count1, min.Count);

			for (int i = 0; i < count2; i++)
				this.bits[i] = min[i] ^ max[i];
			for (int i = count2; i < count1; i++)
				this.bits[i] = max[i];

			if (this._FixedSize == true)
			{
				for (int i = count1; i < this.Units; i++)
					this.bits[i] = 0;
			}
		}

		protected void Add(BigNumBase integer)
		{
			if (this._IsNaN || integer._IsNaN)
			{
				this.SetToNaN();
				return;
			}

			if (this._IsNegative != integer._IsNegative)
			{
				integer._IsNegative = !integer._IsNegative;
				this.Subtract(integer);
				integer._IsNegative = !integer._IsNegative;
				return;
			}

			if (this._IsInfinite || integer._IsInfinite)
			{
				this.SetToInfinite();
				return;
			}

			List<Unit> min;
			List<Unit> max;
			if (this.bits.Count < integer.bits.Count)
			{
				min = this.bits;
				max = integer.bits;
			}
			else
			{
				min = integer.bits;
				max = this.bits;
			}

			ulong r = 0;
			for (int i = 0; i < min.Count; i++)
			{
				ulong val = (ulong)min[i] + (ulong)max[i] + r;
				r = val >> 32;
				this.bits[i] = (uint)val;
			}

			for (int i = min.Count; i < this.Units; i++)
			{
				ulong val = (ulong)max[i] + r;
				r = val >> 32;
				this.bits[i] = (uint)val;
			}

			if (this._FixedSize == false)
			{
				for (int i = this.Units; i < max.Count; i++)
				{
					ulong val = (ulong)max[i] + r;
					r = val >> 32;
					this.bits.Add((uint)val);
				}

				if (r > 0 )
					this.bits.Add((uint)r);

				while (this.bits.Count > BigNumBase.MinUnits && this.bits.Last() == 0)
					this.bits.RemoveLast();
			}
		}

		protected void Subtract(BigNumBase integer)
		{
			if (this._IsNaN || integer._IsNaN)
			{
				this.SetToNaN();
				return;
			}

			if (this._IsNegative != integer._IsNegative)
			{
				integer._IsNegative = !integer._IsNegative;
				this.Add(integer);
				integer._IsNegative = !integer._IsNegative;
				return;
			}

			if (this._IsInfinite && integer._IsInfinite)
			{
				throw new InvalidOperationException("The difference between positive and negative infinity cannot be evaluated.");
			}
			if (this._IsInfinite)
			{
				return;
			}
			if (integer._IsInfinite)
			{
				this.SetToInfinite();
				this._IsNaN = integer._IsNegative;
			}

			if (this.IsEqualTo(integer) == true)
			{
				this.SetToZero();
				return;
			}

			List<Unit> min;
			List<Unit> max;
			bool isNegative = this._IsNegative;
			this._IsNegative = false;
			integer._IsNegative = false;

			if (this.IsSmallerThan(integer) == true)
			{
				min = this.bits;
				max = integer.bits;
				this._IsNegative = !isNegative;
			}
			else
			{
				min = integer.bits;
				max = this.bits;
				this._IsNegative = isNegative;
			}
			integer._IsNegative = isNegative;

			uint r = 0;
			for (int i = 0; i < min.Count; i++)
			{
				long val = (long)max[i] - (long)min[i] - r;
				r = 0;
				while (val < 0)
				{
					val += uint.MaxValue;
					r += 1;
				}
				this.bits[i] = (uint)((ulong)val);
			}

			for (int i = min.Count; i < this.Units; i++)
			{
				long val = (long)max[i] - r;
				r = 0;
				while (val < 0)
				{
					val += uint.MaxValue;
					r += 1;
				}
				this.bits[i] = (uint)((ulong)val);
			}

			if (this._FixedSize == false)
			{
				for (int i = this.Units; i < max.Count; i++)
				{
					long val = (long)max[i] - r;
					r = 0;
					while (val < 0)
					{
						val += uint.MaxValue;
						r += 1;
					}
					this.bits.Add((uint)((ulong)val));
				}
				if (r > 0)
					throw new Exception("Error");

				while (this.bits.Count > BigNumBase.MinUnits && this.bits.Last() == 0)
					this.bits.RemoveLast();
			}
		}

		private static void Add(Unit[] bits, int index, ulong val)
		{
			while (val > 0)
			{
				val = bits[index] + val;
				bits[index] = (Unit)val;
				val = val >> 32;
				index++;
			}
		}

		protected void Multiply(BigNumBase integer)
		{
			BigNumBase zero = BigNumBase.Zero;
			if (this.IsEqualTo(zero) || integer.IsEqualTo(zero))
			{
				this.SetToZero();
				return;
			}
			if (this._IsInfinite || integer._IsInfinite)
			{
				this.SetToInfinite();
				return;
			}
			if (this._IsNaN || integer._IsNaN)
			{
				this.SetToNaN();
				return;
			}

			int size = this.Units;
			if (this._FixedSize == false)
				size += integer.Units;
			Unit[] bits = new Unit[size];
			for (int i = 0; i < this.Units; i++)
			{
				for (int j = 0; j < integer.Units; j++)
				{
					int index = i + j;
					if (index >= size)
						continue;
					ulong val = (ulong)this.bits[i] * (ulong)integer.bits[j];
					BigNumBase.Add(bits, index, val & uint.MaxValue);
					if (index+1 >= size)
						continue;
					BigNumBase.Add(bits, index + 1, val >> 32);
				}
			}
			this.bits.Clear();
			this.bits.AddRange(bits);
			this.RemoveLeadingZeros();
			this._IsNegative = this._IsNegative != integer._IsNegative;
		}

		protected void Divide(BigNumBase integer, out BigNumBase remainder)
		{
			remainder = BigNumBase.Zero;
			if (this._IsNaN || integer._IsNaN)
			{
				this.SetToNaN();
				return;
			}
			if (this._IsInfinite && integer._IsInfinite)
			{
				throw new InvalidOperationException("Cannot evaluate infinity/infinity");
			}
			if (this._IsInfinite)
			{
				this._IsNegative = this._IsNegative != integer._IsNegative;
				return;
			}
			if (integer._IsInfinite)
			{
				this.SetToZero();
				return;
			}
			if (integer.IsEqualTo(remainder) == true)
			{
				if (this.IsEqualTo(remainder))
					throw new InvalidOperationException("Cannot evaluate 0/0");

				bool isNegative = this._IsNegative;
				this.SetToZero();
				this._IsNegative = isNegative;
				this._IsInfinite = true;
				return;
			}

			Unit[] bits = new Unit[this.Units];
			bool divIsNegative = integer._IsNegative;
			integer._IsNegative = false;
			remainder = new BigNumBase(false, false, new List<Unit>(integer.Units));
			for (int i = this.Units-1; i > -1; i--)
			{
				for (int j = BigNumBase.UnitSize-1; j > -1; j--)
				{
					remainder.ShiftLeft(1);
					remainder.bits[0] |= (this.bits[i] & (1u << j)) >> j;
					if (integer.IsEqualTo(remainder))
					{
						remainder.SetToZero();
						bits[i] |= 1u << j;
					}
					else if (integer.IsSmallerThan(remainder))
					{
						remainder.Subtract(integer);
						bits[i] |= 1u << j;
					}
				}
			}
			integer._IsNegative = divIsNegative;
			this._IsNegative = this._IsNegative != integer._IsNegative;
			this.bits.Clear();
			this.bits.AddRange(bits);
			this.RemoveLeadingZeros();
			remainder._IsNegative = this._IsNegative;
		}

		protected bool IsEqualTo(BigNumBase integer)
		{
			if (this._IsNaN && integer._IsNaN)
				return true;
			if ((this._IsInfinite && integer._IsInfinite) && (this._IsNegative && integer._IsNegative))
				return true;

			List<Unit> min;
			List<Unit> max;
			if (this.Units < integer.Units)
			{
				min = this.bits;
				max = integer.bits;
			}
			else
			{
				min = integer.bits;
				max = this.bits;
			}

			for (int i = min.Count; i < max.Count; i++)
			{
				if (max[i] != 0)
					return false;
			}
			for (int i = 0; i < min.Count; i++)
			{
				if (min[i] != max[i])
					return false;
			}

			return ((this._IsInfinite == integer._IsInfinite) && (this._IsNaN == integer._IsNaN));
		}

		protected bool IsSmallerThan(BigNumBase integer)
		{
			if (this._IsNegative == true && integer._IsNegative == false)
				return true;
			if (this._IsNegative == false && integer._IsNegative == true)
				return false;

			if (this._IsNaN || integer._IsNaN)
				throw new InvalidOperationException("Cannot compare NaN's.");

			if (this._IsInfinite && integer._IsInfinite)
			{
				if (this._IsNegative == integer._IsNegative)
					throw new InvalidOperationException("Cannot compare infinite numbers with the same sign.");
				return this._IsNegative;
			}
			if (this._IsInfinite)
				return this._IsNegative;
			if (integer._IsInfinite)
				return !integer._IsNegative;

			bool? RetVal = null;
			if (integer.Units < this.Units)
			{
				for (int i = this.Units - 1; i >= integer.Units; i--)
				{
					if (this.bits[i] != 0)
					{
						RetVal = false;
						break;
					}
				}
			}
			else if (this.Units < integer.Units)
			{
				for (int i = integer.Units - 1; i >= this.Units; i--)
				{
					if (integer.bits[i] != 0)
					{
						RetVal = true;
						break;
					}
				}
			}
			if (RetVal == null)
			{
				for (int i = this.Units - 1; i > -1; i--)
				{
					if (this.bits[i] == integer.bits[i])
						continue;

					if (this.bits[i] < integer.bits[i])
						RetVal = true;
					else
						RetVal = false;
					break;
				}
				if (RetVal == null)
					return false;
			}

			if (this._IsNegative == false)
				return (bool)RetVal;
			else
				return !(bool)RetVal;
		}

		protected bool IsGreaterThan(BigNumBase integer)
		{
			if (this._IsNegative == true && integer._IsNegative == false)
				return false;
			if (this._IsNegative == false && integer._IsNegative == true)
				return true;

			if (this._IsNaN || integer._IsNaN)
				throw new InvalidOperationException("Cannot compare NaN's.");

			if (this._IsInfinite && integer._IsInfinite)
			{
				if (this._IsNegative == integer._IsNegative)
					throw new InvalidOperationException("Cannot compare infinite numbers with the same sign.");
				return !this._IsNegative;
			}
			if (this._IsInfinite)
				return !this._IsNegative;
			if (integer._IsInfinite)
				return integer._IsNegative;

			bool? RetVal = null;
			if (integer.Units < this.Units)
			{
				for (int i = this.Units - 1; i >= integer.Units; i--)
				{
					if (this.bits[i] != 0)
					{
						RetVal = true;
						break;
					}
				}
			}
			else if (this.Units < integer.Units)
			{
				for (int i = integer.Units - 1; i >= this.Units; i--)
				{
					if (integer.bits[i] != 0)
					{
						RetVal = false;
						break;
					}
				}
			}
			if (RetVal == null)
			{
				for (int i = this.Units - 1; i > -1; i--)
				{
					if (this.bits[i] == integer.bits[i])
						continue;

					if (this.bits[i] > integer.bits[i])
						RetVal = true;
					else
						RetVal = false;
					break;
				}
				if (RetVal == null)
					return false;
			}

			if (this._IsNegative == false)
				return (bool)RetVal;
			else
				return !(bool)RetVal;
		}
		#endregion

		#region Public Methods
		public bool GetBit(int bitIndex)
		{
			if (bitIndex >= this.Units * BigNumBase.UnitSize)
				throw new IndexOutOfRangeException();

			int index = bitIndex / BigNumBase.UnitSize;
			bitIndex = bitIndex % BigNumBase.UnitSize;
			bitIndex = 1 << bitIndex;
			return (this.bits[index] & bitIndex) == bitIndex;
		}

		public virtual int[] GetBits()
		{
			int[] bits = new int[this.Units+1];
			for (int i = 0; i < this.Units; i++)
				bits[i] = (int)this.bits[i];
			bits[this.Units] = (int)this.Properties.Value;
			return bits;
		}

		public override string ToString()
		{
			return this.ToStringCore(null, null);
		}
		#endregion

		#region Static Methods
		public static bool IsInfinite(BigNumBase number) { return number.Properties.HasFlag(NumberProperties.IsInfinite); }
		public static bool IsPositiveInfinite(BigNumBase number) 
		{ 
			return number.Properties.HasFlag(NumberProperties.IsInfinite) && !number.Properties.HasFlag(NumberProperties.IsNegative);
		}
		public static bool IsNegativeInfinite(BigNumBase number)
		{
			return number.Properties.HasFlag(NumberProperties.IsInfinite) && number.Properties.HasFlag(NumberProperties.IsNegative);
		}
		public static bool IsNan(BigNumBase number) { return number.Properties.HasFlag(NumberProperties.IsNaN); }
		#endregion

		#region ILinearScalar
		protected virtual string ToStringCore(string format, IFormatProvider formatProvider) { throw new NotImplementedException(); }
		string IFormattable.ToString(string format, IFormatProvider formatProvider)
		{
			return this.ToStringCore(format, formatProvider);
		}

		protected virtual bool IsEqualToCore(IScalar scalar) { throw new NotImplementedException(); }
		bool IScalar.IsEqualTo(IScalar scalar)
		{
			return this.IsEqualToCore(scalar);
		}

		protected virtual IScalar DivideCore(IScalar scalar) { throw new NotImplementedException(); }
		IScalar IScalar.Divide(IScalar scalar)
		{
			return this.DivideCore(scalar);
		}

		protected virtual IScalar SubtractCore(IScalar scalar) { throw new NotImplementedException(); }
		IScalar IScalar.Subtract(IScalar scalar)
		{
			return this.SubtractCore(scalar);
		}

		protected virtual IScalar MultiplyCore(IScalar scalar) { throw new NotImplementedException(); }
		IScalar IScalar.Multiply(IScalar scalar)
		{
			return this.MultiplyCore(scalar);
		}

		protected virtual IScalar AddCore(IScalar scalar) { throw new NotImplementedException(); }
		IScalar IScalar.Add(IScalar scalar)
		{
			return this.AddCore(scalar);
		}

		protected virtual IOperand GetCopyCore() { throw new NotImplementedException(); }
		IOperand IOperand.GetDeepCopy()
		{
			return this.GetCopyCore();
		}

		protected virtual bool IsSmallerThanCore(ILinearScalar scalar) { throw new NotImplementedException(); }
		bool ILinearScalar.IsSmallerThan(ILinearScalar scalar)
		{
			return this.IsSmallerThanCore(scalar);
		}

		protected virtual bool IsGreaterThanCore(ILinearScalar scalar) { throw new NotImplementedException(); }
		bool ILinearScalar.IsGreaterThan(ILinearScalar scalar)
		{
			return this.IsGreaterThanCore(scalar);
		}

		int IComparable.CompareTo(object obj)
		{
			ILinearScalar scalar = (ILinearScalar)obj;
			if (this.IsEqualToCore(scalar))
				return 0;
			if (this.IsSmallerThanCore(scalar))
				return -1;
			return 1;
		}
		#endregion

		#region Subtypes
		[Flags]
		public enum NumberProperties : int
		{
			None = 0,
			IsNegative = 1,
			FixedSize = 1 << 1,
			IsNaN = 1 << 2,
			IsInfinite = 1 << 3,
		}
		#endregion
	}
}
